Section: New Results

Random Graph and Matrix Models

Participants : Arun Kadavankandy, Konstantin Avrachenkov.

In [27] A. Kadavankandy and K. Avrachenkov in collaboration with L. Cottatellucci (EURECOM , France) and R. Sundaresan (IIS Bangalore, India) propose a local message passing algorithm based on Belief Propagation (BP) to detect a small hidden Erdös-Rényi (ER) subgraph embedded in a larger sparse ER random graph in the presence of side-information. The side-information considered is in the form of revealed subgraph nodes called cues, some of which may be erroneous. Namely, the revealed nodes may not all belong to the subgraph, and it is not known to the algorithm a priori which cues are correct and which are incorrect. The authors show that asymptotically as the graph size tends to infinity, the expected fraction of misclassified nodes approaches zero for any positive value of a parameter $\lambda$, which represents the effective Signal-to-Noise Ratio of the detection problem. Previous works on subgraph detection using BP without side-information showed that BP fails to recover the subgraph when $\lambda <1/e$. These new results thus demonstrate the substantial gains in having even a small amount of side-information.

PageRank has numerous applications in information retrieval, reputation systems, machine learning, and graph partitioning. In [8] K. Avrachenkov and A. Kadavankandy in collaboration with L. Ostroumova and A. Raigorodskii (Yandex, Russia) study PageRank in undirected random graphs with an expansion property. The Chung-Lu random graph is an example of such a graph. They show that in the limit, as the size of the graph goes to infinity, PageRank can be approximated by a mixture of the restart distribution and the vertex degree distribution. They also extend the result to Stochastic Block Model (SBM) graphs, where they show that there is a correction term that depends on the community partitioning.